package com.feiyue.learning.graph;

import java.util.Scanner;

/**
 * 最短路径算法（处理负权边）
 * @author  feiyue
 * @date  2020/4/6
 */
public class Bellman_ford {

    public static void main(String[] args) {

        // 顶点数
        int n = 9;

        // 图实际边数（图不含回路）
        int m = 8;

        // 表示无穷大
        int inf = 99999;

        // 图各个边起始顶点
        int[] u = new int[10];

        // 图各个边终止顶点
        int[] v = new int[10];

        // 图各个边的权重
        int[] w = new int[10];

        // 初始化各个边信息
        for (int i = 1; i <=m; i++) {
            Scanner sc = new Scanner(System.in);
            u[i] = sc.nextInt();    // 第 i 条边起始顶点为 u[i]
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        // 用于存放源点到各个顶点的初始路程
        int[] dis = new int[10];
        for (int i = 1; i <= n; i++) {
            dis[i] = inf;
        }
        dis[1] = 0; // 自身到自身为 0

        /*
         * Bellman-ford 核心算法
         *  1、外层循环, 首次是源点只经过一条边到达其他各顶点的最短距离, 第二次只经过两条边, 以此类推
         *  2、内层循环, 每层循环对其中一条边进行松弛操作
         */
        for (int i = 1; i <= n-1; i++) {
            for (int j = 1; j <= m; j++) {
                if (dis[v[j]] > dis[u[j]] + w[j]) {
                    dis[v[j]] = dis[u[j]] + w[j];
                }
            }
        }

        boolean flag = false;
        for (int j = 1; j <= m; j++) {
            if (dis[v[j]] > dis[u[j]] + w[j]) {
                flag = true;
            }
        }
        if (flag) {
            System.out.println("图中包含负权回路");
        }
    }
}
